package heap.medium;

import java.util.PriorityQueue;


/**
 * 最接近原点的 K 个点
 * 示例 1：
 *
 * 输入：points = [[1,3],[-2,2]], K = 1
 * 输出：[[-2,2]]
 * 解释：
 * (1, 3) 和原点之间的距离为 sqrt(10)，
 * (-2, 2) 和原点之间的距离为 sqrt(8)，
 * 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
 * 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
 * 示例 2：
 *
 * 输入：points = [[3,3],[5,-1],[-2,4]], K = 2
 * 输出：[[3,3],[-2,4]]
 * （答案 [[-2,4],[3,3]] 也会被接受。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/k-closest-points-to-origin
 */
public class KClosestPointsToOrigin_973 {

    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {
            double bsqrt = Math.sqrt(Math.pow(b[0], 2) + Math.pow(b[1], 2));
            double asqrt = Math.sqrt(Math.pow(a[0], 2) + Math.pow(a[1], 2));
            return bsqrt > asqrt ? 1 : -1;
        });
        for (int[] point : points) {
            maxHeap.offer(point);
            if (maxHeap.size() > k)
                maxHeap.poll();
        }

        int[][] arr = new int[maxHeap.size()][2];
        int i = 0;
        while(!maxHeap.isEmpty()) {
            int[] poll = maxHeap.poll();
            arr[i][0] = poll[0];
            arr[i][1] = poll[1];
            i++;
        }
        return arr;
    }

    public static void main(String[] args) {
        KClosestPointsToOrigin_973 kp = new KClosestPointsToOrigin_973();

        for (int[] a : kp.kClosest(new int[][]{{3,3}, {5,-1}, {-2, 4}}, 2)) {
            System.out.println(a[0] + " " + a[1]);
        }
    }
}
